package com.sise.Tree;

/**
 *      剑指 Offer 54. 二叉搜索树的第 k 大节点
 *
 *      输入: root = [5,3,6,2,4,null,null,1], k = 3
 *
 *            5
 *           / \
 *          3   6
 *         / \
 *        2   4
 *       /
 *      1
 *
 *      输出: 4
 *
 *      解题思路：
 *      将中序遍历反过来即可，中序遍历为 左根右，换为右根左

 */
public class _offer_54_kthLargest {

//    public static void main(String[] args) {
//        Integer[] array = new Integer[]{5,3,6,2,4,null,null,1};
//        TreeNode root = convert(array);
//        kthLargest(root,3);
//        System.out.println(res);
//    }

    // 这里将 res、k 都提取为 全局变量，都是由于结果的唯一性，
    // 如果将 k 作为方法参数向下递归，那么一开始假设 k = 1，向下传递后会改变，但返回原函数 k 又保持不变，会导致前面的值被覆盖
    int res;
    int k;
    public int kthLargest(TreeNode root, int k) {
        // 将传递的参数 赋值给 全局参数
        this.k = k;
        helper(root);
        return res;
    }

    // 递归
    public void helper(TreeNode root){
        // 如果节点为空，说明已经到底了，k < 0 截止
        if (root == null || k < 0) return ;
        helper(root.right);
        // 将 K 降低到 0，那就说明此时为第 K 大数值
        if (--k == 0){
            res = root.val;     // 赋值
            return ;            // 返回上一层主调函数
        }
        helper(root.left);
    }
}
